In some situations, a number of different units (e.g., hardware or software units) will share a limited resource. For example, a number of modules in a network device might provide packets that will be processed via a single pipeline. Moreover, two or more of these units might simultaneously need to access the resource. In order to determine which of the units will be able to access the resource, an arbitration unit can be provided.
For example, FIG. 1 is a block diagram of a known arbitration unit 100. The arbitration unit 100 receives information from a number of units that might request access to a limited resource (i.e., “requesters” 0 through N−1). The received information might indicate, for example, whether or not a particular requester currently needs to access the resource. Based on the received information, the arbitration unit 100 selects one of the requesters.
In a sequential priority encoding scheme, the arbitration unit 100 sequentially examines the information received from each requester and selects the first requester that needs to access a resource. Assume, for example, that the arbitration unit 100 receives information from ten requesters—and that only the third and seventh requesters currently need to access the resource. In this case, the arbitration unit 100 first evaluates information received from the first and second requesters (and does not select either of those requesters because neither needs to access the resource). The arbitration unit 100 then evaluates information received from the third requester—and provides an indication that the “selected requester” is the third requester. The third requester is then allowed to access the resource (e.g., a packet from that resource might be processed via a pipeline in a network device).
Consider an arbitration unit 100 that receives a bit r[0] from a first requester, where r[0] can equal “0” (indicating that the first requester is not currently seeking access to a resource) or “1” (indicating that the first requester is currently seeking access to the resource). Similarly, the arbitration unit 100 receives r[1], r[2], . . . r[N−1] from other requesters. In this case, the Selected_Requester (i.e., having a value from 0 through N−1) can be calculated as follows:                If (r[0]) Selected_Requester=0;        Else if (r[1]) Selected_Requester=1;        Else if (r[2]) Selected_Requester=2;        . . .        Else if (r[N−1]) Selected_Requester=N−1There is a disadvantage, however, with calculating Selected_Requester in this traditional way. In particular, the calculation may take a significant amount of time, especially when there are a large number of requesters. For example, when N equals one hundred (i.e., there are one hundred requesters), the calculation might require up to 100 sequential logic gates. As a result, the selection of a requester might take more than one clock cycle to process.        